//
//  ProblemOffer26.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/9.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 26. 树的子结构
 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
 B是A的子结构， 即 A中有出现和B相同的结构和节点值。

 例如:
 给定的树 A:
      3
     / \
    4   5
   / \
  1   2
 给定的树 B：
    4
   /
  1
 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

 示例 1：
     输入：A = [1,2,3], B = [3,1]
     输出：false
 示例 2：
     输入：A = [3,4,5,1,2], B = [4,1]
     输出：true
 限制：0 <= 节点个数 <= 10000
 */
@objcMembers class ProblemOffer26: NSObject {
    func solution() {
        let A1 = TreeNode(1)
        A1.left = TreeNode(2)
        A1.right = TreeNode(3)
        let B1 = TreeNode(3)
        B1.left = TreeNode(1)
        print(isSubStructure(A1, B1))
        
        
        let A2 = TreeNode(3)
        A2.left = TreeNode(4)
        A2.left?.left = TreeNode(1)
        A2.left?.right = TreeNode(1)
        A2.right = TreeNode(5)
        let B2 = TreeNode(4)
        B2.left = TreeNode(1)
        print(isSubStructure(A2, B2))
        
        
    }
    // 深度优先搜索 递归
    func isSubStructure(_ A: TreeNode?, _ B: TreeNode?) -> Bool {
        if A == nil && B == nil {
            return true
        } else if A != nil && B != nil {
            if A!.val == B!.val {
                if isEqual(A, B) == true {
                    return true
                }
            }
            if  isSubStructure(A?.left, B) == true {
                return true
            }
            return isSubStructure(A?.right, B)
        }
        return false
    }
    
    func isEqual(_ A: TreeNode?, _ B: TreeNode?) -> Bool {
        if A == nil && B == nil {
            return true
        } else if A != nil && B != nil {
            return A!.val == B!.val && isEqual(A?.left, B?.left) && isEqual(A?.right, B?.right)
        } else if A != nil && B == nil {
            return true
        } else {
            return false
        }
    }
}
